// 12.2 动态数组
/**
 * new和delete运算符一次分配/释放一个对象，但某些应用需要一次为很多对象分配内存的功能。
 * 为了支持这种需求，C++语言和标准库提供了两种一次分配一个对象数组的方法。C++语言定义了另一种new表达式语法，可以分配并初始化一个对象数组。
 * 很多（可能是大多数）应用都没有直接访问动态数组的需求。
 * 大多数应用应该使用标准库容器而不是动态分配的数组。使用容器更为简单、更不容易出现内存管理错误并且可能有更好的性能。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;

int main()
{
    // 12.2.2 allocator类
    // 当分配一大块内存时，我们通常计划在这块内存上按需构造对象。在此情况下，我们希望将内存分配和对象构造分离。
    // 这意味着我们可以分配大块内存，但只在真正需要时才真正执行对象创建操作（同时付出一定开销）。

    // allocaotr类
    // 标准库allocator类定义在头文件memory中，它帮助我们将内存分配和对象构造分离开来。
    // 它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。
    // 类似vector，allocator是一个模板（参见3.3节，第86页）。
    allocator<string> alloc;          // 可以分配string的allocator对象
    auto const p = alloc.allocate(6); // 分配6个未初始化的string
    // allocator支持的操作：
    // 1. allocator<T> a 定义了一个名为a的allocator对象，它可以为类型T的对象分配内存
    // 2. a.allocate(n) 分配一段原始的、未构造的内存，保存n个类型为T的对象
    // 3. a.deallocate(p,n) 释放从T*指针p中地址开始的内存，这段内存保存了n个类型为T的对象；
    //                      p必须是先前由allocate返回的指针，且n必须是p创建时要求的大小。
    //                      在调用deallocate前，用户必须对每个在这块内存中创建的对象调用destroy
    // 4. a.construct(p,args) p必须是类型为T*的指针，指向一块原始内存；args被传递给类型为T的构造函数，用来在p的内存中构造一个对象
    // 5. a.destroy(p) p为T*类型的指针，此算法对p指向的对象执行析构函数

    // allocator分配未构造的内存
    // allocator分配的内存是未构造的（unconstructed）。
    // 在新标准库中，construct成员函数接受一个指针和零个或多个额外参数，在给定位置构造一个元素。额外参数用来初始化构造的对象。类似make_shared
    auto q = p;                    // q指向最后构造的元素之后的位置
    alloc.construct(q++);          // *q为空字符串
    alloc.construct(q++, 10, 'c'); // *q为cccccccccc
    alloc.construct(q++, "hi");    // *q为hi
    // 还未构造对象的情况下就使用原始内存是错误的
    // 为了使用allocate返回的内存，我们必须用construct构造对象。使用未构造的内存，其行为是未定义的。
    // 当我们用完对象后，必须对每个构造的元素调用destroy来销毁它们。
    // 函数destroy接受一个指针，对指向的对象执行析构函数（参见12.1.1节，第402页）：[插图]
    while (q != p)
    {
        alloc.destroy(--q); // 释放我们真正构造的string
    }
    // 一旦元素被销毁后，就可以重新使用这部分内存来保存其他string，也可以将其归还给系统。
    // 释放内存通过调用deallocate来完成：[插图]
    alloc.deallocate(p, 6); // 注意是之前allocate时的6，而不是能是5或7，或者其他数值

    // 拷贝和填充未初始化内存的算法
    // 标准库还为allocator类定义了两个伴随算法，可以在未初始化内存中创建对象。
    // 表12.8描述了这些函数，它们都定义在头文件memory中。[插图]
    // 1. uninitialized_copy(b,e,b2) 从迭代器范围b、e中拷贝元素到迭代器b2指定的未构造的原始内存中。
    // 2. uninitialized_copy_n(b,n,b2) 从迭代器b指向的元素开始，拷贝n个元素到b2开始的内存中
    // 3. uninitialized_fill(b,e,t) 在迭代器返回b、e指定的原始内存范围中创建对象，对象的值均为t的拷贝
    // 4. uninitialized_fill_n(b,n,t) 从迭代器b指向的内存地址开始创建n个对象。
    vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    allocator<int> alloc1;
    auto p1 = alloc1.allocate(vi.size() * 2);               // 分配比vi中元素所占空间大一倍的动态内存
    auto q1 = uninitialized_copy(vi.begin(), vi.end(), p1); // 通过拷贝vi中的元素来构造从p1开始的元素
    cout << *p1 << endl; // 0
    cout << *q1 << endl; // 10
    uninitialized_fill_n(q1, vi.size(), 42); // 将剩余元素初始化为42
    cout << *p1 << endl; // 0
    cout << *q1 << endl; // 42
    while (p1 != q1)
    {
        cout << *q1-- << endl; // 42 9 8 7 6 5 4 3 2 1
    }
    // 传递给uninitialized_copy的目的位置迭代器必须指向未构造的内存。与copy不同，uninitialized_copy在给定目的位置构造元素。
    // 类似copy，uninitialized_copy返回（递增后的）目的位置迭代器。
    // 因此，一次uninitialized_copy调用会返回一个指针，指向最后一个构造的元素之后的位置。

    return 0;
}